package dfs

import (
	"sort"
)

func absInt(a, b int) int {
	if a-b > 0 {
		return a - b
	} else {
		return b - a
	}
}

func ThreeSumClosest(nums []int, target int) int {
	// 排序
	sort.Ints(nums)

	// 首先找到最接近结果的相邻位置
	var leftPos, rightPos, midPos int
	leftPos = 0
	midPos = 1
	rightPos = 2

	var nearestSub = absInt(target, nums[leftPos]+nums[midPos]+nums[rightPos])
	nearestLeftPos, nearestMidPos, nearestRightPos := leftPos, midPos, rightPos
	for rightPos < len(nums) {
		currentSub := absInt(target, nums[leftPos]+nums[midPos]+nums[rightPos])
		if currentSub < nearestSub {
			nearestLeftPos, nearestMidPos, nearestRightPos = leftPos, midPos, rightPos
			nearestSub = currentSub
		}
		leftPos++
		midPos++
		rightPos++
	}
	leftPos, midPos, rightPos = nearestLeftPos, nearestMidPos, nearestRightPos

	lowestDistance := absInt(target, nums[leftPos]+nums[midPos]+nums[rightPos])
	ret := nums[leftPos] + nums[midPos] + nums[rightPos]
	hasVisitMidPos := make(map[int]string)
	hasVisitMidPos[midPos] = "1"
	for {
		if nums[leftPos]+nums[midPos]+nums[rightPos]-target > 0 {
			leftPos--
			if leftPos < 0 {
				leftPos++
				if midPos > 0 && midPos-1 != leftPos {
					midPos--
					if "" != hasVisitMidPos[midPos] {
						break
					} else {
						hasVisitMidPos[midPos] = "1"
					}
				} else {
					break
				}
			}
		} else {
			rightPos++
			if rightPos >= len(nums) {
				rightPos--
				if midPos < len(nums)-1 && midPos+1 != rightPos {
					midPos++
					if "" != hasVisitMidPos[midPos] {
						break
					} else {
						hasVisitMidPos[midPos] = "1"
					}
				} else {
					break
				}
			}
		}
		currentDistance := absInt(target, nums[leftPos]+nums[midPos]+nums[rightPos])
		if lowestDistance > currentDistance {
			lowestDistance = currentDistance
			ret = nums[leftPos] + nums[midPos] + nums[rightPos]
		}
	}
	return ret
}
